这道题还是树的板题,先将个信息插入字典树中,对于查询的密码,在字典树中查询即可。
插入很好办,我们现在来讨论查询操作。我们记为任意一个信息,是待匹配的密码。表示有多少个字符串经过点,表示有多少个字符串以点结尾。
那么会出现三种情况:
1.是的前缀,累加路径上所有的即可。
2.。其实就是情况1,结束时的点一定与结束时的点相同,也就包含在中。
3.是的前缀,如果单词最后一个字符所在节点为,我们很容易看出就代表该单词是多少字符串的前缀。那么我们只需要加上就好了。
但是,会包含以节点结尾的单词数,所以结果须减去。
那么,一道难蓝题就被我们解决了,附上代码:
#include <cstdio>
#include <cstring>
const int MAXN = 500000;
int n,m,len;
int Trie[ MAXN + 5 ][ 2 ] , cnt;
int tot[ MAXN + 5 ] , fin[ MAXN + 5 ];
void Insert( char *str , int len ) {
int u = 0;
for( int i = 0 ; i < len ; i ++ ) {
int num = str[ i ] - '0';
if( !Trie[ u ][ num ] )
Trie[ u ][ num ] = ++ cnt;
u = Trie[ u ][ num ];
tot[ u ] ++;
}
fin[ u ] ++;
}
int Find( char *str , int len ) {
int u = 0 , Ans = 0;
for( int i = 0 ; i < len ; i ++ ) {
int num = str[ i ] -'0';
if( !Trie[ u ][ num ] )
return Ans;
u = Trie[ u ][ num ];
Ans += fin[ u ];
}
return Ans - fin[ u ] + tot[ u ];
}
int s1;
char s[ 10005 ];
int main( ) {
scanf("%d %d",&m,&n);
for( int i = 1 ; i <= m ; i ++ ) {
scanf("%d",&len);
for( int j = 0 ; j < len ; j ++ ) {
scanf("%d",&s1);
s[ j ] = s1 + '0';
}
Insert( s , len );
}
for( int i = 1 ; i <= n ; i ++ ) {
scanf("%d",&len);
for( int j = 0 ; j < len ; j ++ ) {
scanf("%d",&s1);
s[ j ] = s1 + '0';
}
printf("%d\n",Find( s , len ));
}
return 0;
}